package com.mlamp.排序算法;

import java.util.Arrays;

public class 归并排序 {
    public static void main(String[] args) {
        int[] ints = 基础排序.generateArray(30);
        int[] ints1 = mergeSort(ints);
        System.out.println(Arrays.toString(ints1));
    }


    public static int[] mergeSoft3(int[] array) {
        if (array.length < 2) return array;
        int mid = (array.length >> 1);
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        return merge3(mergeSoft3(left), mergeSoft3(right));
    }

    private static int[] merge3(int[] mergeSoft3, int[] mergeSoft31) {
        int[] result = new int[mergeSoft3.length + mergeSoft31.length];
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
            if (i >= mergeSoft3.length) {
                result[index++] = mergeSoft31[j++];
            } else if (j >= mergeSoft31.length) {
                result[index++] = mergeSoft3[i++];
            } else if (mergeSoft3[i] > mergeSoft31[j]) {
                result[index++] = mergeSoft31[j++];
            } else {
                result[index++] = mergeSoft3[i++];
            }
        }
        return result;
    }

    public static int[] mergeSort1(int[] array) {
        if (array.length <= 2) return array;
        int mid = (array.length >> 1);
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        return merge(mergeSort1(left), mergeSort1(right));
    }


    public static int[] mergeSort(int[] array) {
        if (array.length <= 2) return array;
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        return merge2(mergeSort(left), mergeSort(right));
    }

    private static int[] merge2(int[] left, int[] right) {
        int result[] = new int[left.length + right.length];
        for (int idx = 0, i = 0, j = 0; idx < result.length; idx++) {
            if (i >= left.length) {
                result[idx] = right[j++];
            } else if (j >= right.length) {
                result[idx] = left[i++];
            } else if (left[i] > right[j]) {
                result[idx] = right[j];
            } else {
                result[idx] = left[i];
            }
        }
        return result;
    }

    private static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
            if (i >= left.length) {
                result[index] = right[j++];
            } else if (j >= right.length) {
                result[index] = left[i++];
            } else if (left[i] > right[j]) {
                result[index] = right[j++];
            } else {
                result[index] = left[i++];
            }
        }
        return result;
    }
}
